package com.mxw.算法之美.a1数组;

import java.util.ArrayList;
import java.util.List;

public class 边界控制 {



    /**
     * 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
     * 示例:
     * 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
     *
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {

        //大神解法的解读
        int left = 0, right = n-1, top = 0, bottom = n-1;
        int count = 1, target = n * n;
        int[][] res = new int[n][n];
        //for循环中变量定义成i或j的细节：按照通常的思维，i代表行，j代表列
        //这样，就可以很容易区分出来变化的量应该放在[][]的第一个还是第二个
        //对于变量的边界怎么定义：
        //从左向右填充：填充的列肯定在[left,right]区间
        //从上向下填充：填充的行肯定在[top,bottom]区间
        //从右向左填充：填充的列肯定在[right,left]区间
        //从下向上填充：填充的行肯定在[bootom,top]区间
        //通过上面的总结会发现边界的起始和结束与方向是对应的
        while(count <= target){
            //从左到右填充，相当于缩小上边界
            for(int j = left; j <= right; j++) res[top][j] = count++;
            //缩小上边界
            top++;
            //从上向下填充，相当于缩小右边界
            for(int i = top; i <=bottom; i++) res[i][right] = count++;
            //缩小右边界
            right--;
            //从右向左填充，相当于缩小下边界
            for(int j = right; j >= left; j--) res[bottom][j] = count++;
            //缩小下边界
            bottom--;
            //从下向上填充，相当于缩小左边界
            for(int i = bottom; i >= top; i--) res[i][left] = count++;
            //缩小左边界
            left++;
        }
        return res;
    }


    /**
     * 螺旋遍历
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int l = 0, r = matrix[0].length - 1;
        // t：上边。 b：下边
        int t = 0, b = matrix.length - 1;
        int x = 0;
        List<Integer> res = new ArrayList<>();
        while (true) {
            for (int i = l; i <= r; i++) res.add(matrix[t][i]);
            if (++t > b) break;
            for (int i = t; i <= b; i++) res.add(matrix[i][r]);
            if (--r < l) break;
            for (int i = r; i >= l; i--) res.add(matrix[b][i]);
            if (--b < t) break;
            for (int i = b; i >= t; i--) res.add(matrix[i][l]);
            if (++l > r) break;
        }
        return res;
    }

}
